To analyze networks like social media or road maps, we first need a disciplined way to explore them.
- To perform advanced analysis like finding shortest paths, we must first have a way to systematically visit every vertex and edge.
- Structures like social networks, road maps, and the web are all graphs that can be analyzed.
- Traversal is a methodical "sweep" of the graph to collect data like reachability, levels, or timestamps, which are essential for other algorithms.
- The two primary traversal strategies are Breadth-First Search (BFS), which explores layer by layer, and Depth-First Search (DFS), which explores as deeply as possible before backtracking.
- The main goal of traversal is disciplined exploration to understand and record the graph's structure for future use.
Formal Definition: Graph Traversal
A procedure that visits every vertex reachable from a chosen start vertex while tracking order and/or metadata (e.g., parent, level, discovery/finish time).